#include <stdio.h>

#define MAX_NUMBER 1000000000

int fibonacci[50];
int count = 2;

void prepare(void) {
    fibonacci[0] = 1;
    fibonacci[1] = 2;
    while (1) {
        fibonacci[count] = fibonacci[count - 1] + fibonacci[count - 2];
        count++;
        if (fibonacci[count - 1] >= MAX_NUMBER) {
            break;
        }
    }
}

int main(void) {
    prepare();
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        int n;
        scanf("%d", &n);
        int result = 0;
        for (int i = 0; i < 42; i++) {
            int ni = n - fibonacci[i];
            if (ni < 0) {
                break;
            }
            for (int j = i; j < 43; j++) {
                int nj = ni - fibonacci[j];
                if (nj < 0) {
                    break;
                }
                for (int k = j; k < 44; k++) {
                    int nk = nj - fibonacci[k];
                    if (nk < 0) {
                        break;
                    }
                    if (nk == 0) {
                        result++;
                    }
                }
            }
        }
        printf("%d\n", result);
    } 
    return 0;
}
